Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array A = [1,1,2], Your function should return length = 2, and A is now [1,2].
In [8]:
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums_len = len(nums)
if nums_len < 2:
return nums_len
i = 0
j = 0
while j < nums_len:
print(j)
if nums[i] != nums[j]:
i += 1
nums[i] = nums[j]
j += 1
return i + 1
In [9]:
Solution().removeDuplicates([1])
Out[9]:
总是把这句 if nums_len < 2: return nums_len 写成 if nums_len < 2: return nums 结果总是报一些莫名的错误。 Line 58: TypeError: range() integer end argument expected, got list.
一定要注意将数组进行重新安排，不能只返回新数组的长度。
In [19]:
class Solution:
# @param a list of integers
# @return an integer
def removeDuplicates(self, A):
"""
这种方法是将i遍历数组，查找不同的值，
j记录当前对比的值，所以每次找到不同的
值，A[j+1] = A[i]就好
令人疑惑的是A[i] = A[j+1]，为什么要把A[j+1]的值
复制给A[i]呢，i指针会继续加1，根本用不到这一步
"""
if len(A) == 0:
return 0
j = 0
for i in range(0, len(A)):
print(i, j)
if A[i] != A[j]:
A[i], A[j+1] = A[j+1], A[i]
j = j + 1
print(A, 'change', i,j)
return j+1
def removeDuplicates_change(self, A):
"""
事实证明我的想法是对的，唯一的区别在于
其方法保全了整个数组，使其数组中的元素
不会改变，原来是俩个2，后面还是两个2
"""
if len(A) == 0:
return 0
j = 0
for i in range(0, len(A)):
print(i, j)
if A[i] != A[j]:
A[j+1] = A[i]
j = j + 1
print(A, 'change', i,j)
return j+1
In [15]:
Solution().removeDuplicates([1, 2, 2, 3, 3, 3 ,4, 4, 4, 4, 4])
Out[15]:
In [20]:
Solution().removeDuplicates_change([1, 2, 2, 3, 3, 3 ,4, 4, 4, 4, 4])
Out[20]:
In [ ]: